Cleansing uncertain databases leveraging aggregate constraints.

Adaptive system anomaly prediction for large%2Dscale hosting infrastructures.

Incorporating post%2Dclick behaviors into a click model.

MapDupReducer detecting near duplicates over massive datasets.

Computing label%2Dconstraint reachability in graph databases.

Leveraging spatio%2Dtemporal redundancy for RFID data cleansing.

An algorithmic approach to event summarization.

Leveraging spatio%2Dtemporal redundancy for RFID data cleansing.

Optimizing content freshness of relations extracted from the web using keyword search.

Mining Concept%2DDrifting Data Streams.
Recently, mining data streams with concept drifts for actionable insights has become an important and challenging task for a wide range of applications including credit card fraud protection, target marketing, network intrusion detection, etc. Conventional knowledge discovery tools are facing two challenges, the overwhelming volume of the streaming data, and the concept drifts. In this paper, we propose a general framework for mining concept-drifting data streams using weighted ensemble classifiers. We train an ensemble of classification models, such as C4.5, RIPPER, naive Bayesian, etc., from sequential chunks of the data stream. The classifiers in the ensemble are judiciously weighted based on their expected classification accuracy on the test data under the time-evolving environment. Thus, the ensemble approach improves both the efficiency in learning the model and the accuracy in performing classification. Our empirical study shows that the proposed methods have substantial advantage over single-classifier approaches in prediction accuracy, and the ensemble framework is effective for a variety of classification models.
Report on the first international workshop on cloud data management %28CloudDB 2009%29.

Proceedings of the First International CIKM Workshop on Cloud Data Management

Semantic queries in databases problems and challenges.

CloudDB workshop summary.

Learning to rank with a novel kernel perceptron method.

Online Anomaly Prediction for Robust Cluster Systems.

Concept Clustering of Evolving Data.

Weighted Proximity Best%2DJoins for Information Retrieval.
Abstract—We consider the problem of efficiently computing weighted proximity best-joins over multiple lists, with applications in information retrieval and extraction. We are given a multi-termquery,andforeachqueryterm,alistofallitsmatches withscores, sorted by locations. The problemis to findthe overall best matchset, consisting of one match from each list, such that the combined score according to a scoring function is maximized. We study three types of functions that consider both individual match scores and proximity of match locations in scoring a matchset. We present algorithms that exploit the properties of the scoring functions in order to achieve time complexities linear in the size of the match lists. Experiments show that these algorithms greatly outperform the naive algorithm based on taking the cross product of all match lists. Finally, we extend our algorithms for an alternative problem definitionapplicable to information extraction, where we need to find all good matchsets in a document. I.
Inverse Time Dependency in Convex Regularized Learning.

Query Integrity Assurance of Location%2DBased Services Accessing Outsourced Spatial Databases.

Dual encryption for query integrity assurance.

Fast computing reachability labelings for large graphs with high compression rate.
There are numerous applications that need to deal with a large graph and need to query reachability between nodes in the graph. A 2-hop cover can compactly represent the whole edge transitive closure of a graph in O(|V |  · |E | 1/2) space, and be used to answer reachability query efficiently. However, it is challenging to compute a 2-hop cover. The existing approaches suffer from either large resource consumption or low compression rate. In this paper, we propose a hierarchical partitioning approach to partition a large graph G into two subgraphs repeatedly in a top-down fashion. The unique feature of our approach is that we compute 2-hop cover while partitioning. In brief, in every iteration of top-down partitioning, we provide techniques to compute the 2-hop cover for connections between the two subgraphs first. A cover is computed to cut the graph into two subgraphs, which results in an overall cover with high compression for the entire graph G. Two approaches are proposed, namely a node-oriented approach and an edge-oriented approach. Our approach can efficiently compute 2-hop cover for a large graph with high compression rate. Our extensive experiment study shows that the 2-hop cover for a graph with 1,700,000 nodes and 169 billion connections can be obtained in less than 30 minutes with a compression rate about 40,000 using a PC.
Providing freshness guarantees for outsourced databases.
Database outsourcing becomes increasingly attractive as advances in network technologies eliminate the perceived performance difference between in-house databases and outsourced databases, and price advantages of third-party database service providers continue to increase due to economy of scale. However, the potentially explosive growth of database outsourcing is hampered by security concerns, namely data privacy and query integrity of outsourced databases. While privacy issues of outsourced databases have been extensively studied, query integrity for outsourced databases has just started to draw attention from the database community. Currently, there still does not exist a solution that can provide complete integrity. In particular, previous studies have not examined the mechanisms for providing freshness guarantees, that is, the assurance that queries are executed against the most up-to-date data, instead of just some version of the data in the past. Providing a practical solution for freshness guarantees is challenging because continuously monitoring data’s up-to-dateness is expensive. In this paper, we perform a thorough study on how to add freshness guarantees over proposed schemes (including authenticated data structure-based and probabilistic-based approaches) to provide integrity assurance. We implement our solutions and perform extensive experiments to quantify the cost. Our experiment results show that we can provide reasonable tight freshness guarantees without sacrificing much performance. 1.
Modeling and Querying E%2DCommerce Data in Hybrid Relational%2DXML DBMSs.

A Sampling%2DBased Approach to Information Recovery.
Abstract — There has been a recent resurgence of interest in research on noisy and incomplete data. Many applications require information to be recovered from such data. Ideally, an approach for information recovery should have the following features. First, it should be able to incorporate prior knowledge about the data, even if such knowledge is in the form of complex distributions and constraints for which no close-form solutions exist. Second, it should be able to capture complex correlations and quantify the degree of uncertainty in the recovered data, and further support queries over such data. The database community has developed a number of approaches for information recovery, but none is general enough to offer all above features. To overcome the limitations, we take a significantly more general approach to information recovery based on sampling. We apply sequential importance sampling, a technique from statistics that works for complex distributions and dramatically outperforms naive sampling when data is constrained. We illustrate the generality and efficiency of this approach in two application scenarios: cleansing RFID data, and recovering information from published data that has been summarized and randomized for privacy. I.
Fast Graph Pattern Matching.



Efficiently answering reachability queries on very large directed graphs.
Efficiently processing queries against very large graphs is an important research topic largely driven by emerging real world applications, as diverse as XML databases, GIS, web mining, social network analysis, ontologies, and bioinformatics. In particular, graph reachability has attracted a lot of research attention as reachability queries are not only common on graph databases, but they also serve as fundamental operations for many other graph queries. The main idea behind answering reachability queries in graphs is to build indices based on reachability labels. Essentially, each vertex in the graph is assigned with certain labels such that the reachability between any two vertices can be determined by their labels. Several approaches have been proposed for building these reachability labels; among them are interval labeling (tree cover) and 2-hop labeling. However, due to the large number of vertices in many real world graphs (some graphs can easily contain millions of vertices), the computational cost and (index) size of the labels using existing methods would prove too expensive to be practical. In this paper, we introduce a novel graph structure, referred to as pathtree, to help labeling very large graphs. The path-tree cover is a spanning subgraph of G in a tree shape. We demonstrate both analytically and empirically the effectiveness of our new approaches.
Lock%2Dfree consistency control for web 2.0 applications.

Time%2DStamp Management and Query Execution in Data Stream Management Systems.

Location%2DBased Spatial Query Processing in Wireless Broadcast Environments.

Clustering by Pattern Similarity.
Clustering is the process of grouping a set of objects into classes of similar objects. Although definitions of similarity vary from one clustering model to another, in most of these models the concept of similarity is based on distances, e.g., Euclidean distance or cosine distance. In other words, similar objects are required to have close values on at least a set of dimensions. In this paper, we explore a more general type of similarity. Under the pCluster model we proposed, two objects are similar if they exhibit a coherent pattern on a subset of dimensions. For instance, in DNA microarray analysis, the expression levels of two genes may rise and fall synchronously in response to a set of environmental stimuli. Although the magnitude of their expression levels may not be close, the patterns they exhibit can be very much alike. Discovery of such clusters of genes is essential in revealing significant connections in gene regulatory networks. E-commerce applications, such as collaborative filtering, can also benefit from the new model, which captures not only the closeness of values of certain leading indicators but also the closeness of (purchasing, browsing, etc.) patterns exhibited by the customers. Our paper introduces an effective algorithm to detect such clusters, and we perform tests on several real and synthetic data sets to show its effectiveness.
Advances in Web and Network Technologies



Location%2Dbased Spatial Queries with Data Sharing in Wireless Broadcast Environments.
Location-based spatial queries (LBSQs) refer to spatial queries whose answers rely on the location of the inquirer. Efficient processing of LBSQs is of critical importance with the ever-increasing deployment and use of mobile technologies. We show that LBSQs have certain unique characteristics that traditional spatial query processing in centralized databases does not address. For example, a significant challenge is presented by wireless broadcasting environments, which often exhibit high-latency database access. In this paper, we present a novel query processing technique that, while maintaining high scalability and accuracy, manages to reduce the latency considerably in answering location-based spatial queries. Our approach is based on peer-to-peer sharing, which enables us to process queries without delay at a mobile host by using query results cached in its neighboring mobile peers. We illustrate the appeal of our technique through extensive simulation results. 1.
Semantic Data Management Towards Querying Data with their Meaning.

Adaptive Load Diffusion for Multiway Windowed Stream Joins.

GString A Novel Approach for Efficient Search in Graph Databases.
Graphs are widely used for modeling complicated data, including chemical compounds, protein interactions, XML documents, and multimedia. Information retrieval against such data can be formulated as a graph search problem, and finding an efficient solution to the problem is essential for many applications. A popular approach is to represent both graphs and queries on graphs by sequences, thus converting graph search to subsequence matching. State-of-the-art sequencing methods work at the finest granularity – each node (or edge) in the graph will appear as an element in the resulting sequence. Clearly, such methods are not semantic conscious, and the resulting sequences are not only bulky but also prone to complexities arising from graph isomorphism and other problems in searching. In this paper, we introduce a novel sequencing method to capture the semantics of the underlying graph data. We find meaningful components in graph structures and use them as the most basic units in sequencing. It not only reduces the size of resulting sequences, but also enables semantic-based searching. In this paper, we base our approach on chemical compound databases, although it can be applied to searching other complicated graphs, such as protein structures. Experiments demonstrate that our approach outperforms state-ofthe-art graph search methods. 1.
Computing Compressed Multidimensional Skyline Cubes Efficiently.
Recently, the skyline computation and analysis have been extended from one single full space to multidimensional subspaces, which can lead to valuable insights in some applications. Particularly, compressed skyline cubes in the form of skyline groups and their decisive subspaces provide a succinct summarization and compression of multidimensional subspace skylines. However, computing skyline cubes remains a challenging task since the existing methods have to search an exponential number of nonempty subspaces for subspace skylines. In this paper, we propose a novel and efficient method, Stellar, which exploits an interesting skyline group lattice on a small subset of objects which are in the skyline of the full space. We show that this skyline group lattice is easy to compute and can be extended to the skyline group lattice on all objects. After computing the skyline in the full space, Stellar only needs to enumerate skyline groups and their decisive subspaces using the full space skyline objects. Avoiding searching for skylines in an exponential number of subspaces improves the efficiency and the scalability of subspace skyline computation substantially in practice. An extensive performance study verifies the merits of our new method. 1
A Flexible Query Graph Based Model for the Efficient Execution of Continuous Queries.
by
Event summarization for system management.

Load Shedding in Classifying Multi%2DSource Streaming Data A Bayes Risk Approach.
Monitoring multiple streaming sources for collective decision making presents several challenges. First, streaming data are often of large volume, fast speed, and highly bursty nature. Second, it is impossible to offload classification decisions to individual data sources, each of which lacks full knowledge for the decision making. Hence, the central classifier responsible for decision making may be frequently overloaded. In this paper, we study intelligent load shedding for classifying multi-source data. We aim at maximizing classification quality under resource (CPU and bandwidth) constraints. We use a Markov model to predict the distribution of feature values over time. Then, leveraging Bayesian decision theory, we use Bayes risk analysis to model the variances among different data sources in their contributions to the classification quality. We adopt an Expected Observational Risk criterion to quantify the loss of classification quality due to load shedding, and propose a Best Feature First (BFF) algorithm that greedily minimizes such risk. The effectiveness of the approach proposed is confirmed by experiments. 1
Supporting ranking and clustering as generalized order%2Dby and group%2Dby.
The Boolean semantics of SQL queries cannot adequately capture the “fuzzy ” preferences and “soft ” criteria required in non-traditional data retrieval applications. One way to solve this problem is to add a flavor of “information retrieval ” into database queries by allowing fuzzy query conditions and flexibly supporting grouping and ranking of the query results within the DBMS engine. While ranking is already supported by all major commercial DBMSs natively, support of flexibly grouping is still very limited (i.e., group-by). In this paper, we propose to generalize group-by to enable flexible grouping (clustering specifically) of the query results. Different from clustering in data mining applications, our focus is on supporting efficient clustering of Boolean results generated at query time. Moreover, we propose to integrate ranking and clustering with Boolean conditions, forming a new type of ClusterRank query to allow structured data retrieval. Such an integration is nontrivial in terms of both semantics and query processing. We investigate various semantics of this type of queries. To process such queries, a straightforward approach is to simply glue the techniques developed for ranking-only and clustering-only together. This approach is costly since both ranking and clustering are treated as blocking post-processing tasks upon Boolean query results by existing techniques. We propose a summary-based evaluation method that utilizes bitmap index to seamlessly integrate Boolean conditions, clustering, and ranking. Experimental study shows that our approach significantly outperforms the straightforward one and maintains high clustering quality.

BLINKS ranked keyword searches on graphs.
Query processing over graph-structured data is enjoying a growing number of applications. A top-k keyword search query on a graph nds the top k answers according to some ranking criteria, where each answer is a substructure of the graph containing all query keywords. Current techniques for supporting such queries on general graphs suffer from several drawbacks, e.g., poor worst-case performance, not taking full advantage of indexes, and high memory requirements. To address these problems, we propose BLINKS, a bi-level indexing and query processing scheme for top-k keyword search on graphs. BLINKS follows a search strategy with provable performance bounds, while additionally exploiting a bi-level index for pruning and accelerating the search. To reduce the index space, BLINKS partitions a data graph into blocks: The bilevel index stores summary information at the block level to initiate and guide search among blocks, and more detailed information for each block to accelerate search within blocks. Our experiments show that BLINKS offers orders-of-magnitude performance improvement over existing approaches.

Unifying Data and Domain Knowledge Using Virtual Views.
The database community is on a constant quest for better integration of data management and knowledge management. Recently, with the increasing use of ontology in various applications, the quest has become more concrete and urgent. However, manipulating knowledge along with relational data in DBMSs is not a trivial undertaking. In this paper, we introduce a novel, unified framework for managing data and domain knowledge. We provide the user with a virtual view that unifies the data, the domain knowledge and the knowledge inferable from the data using the domain knowledge. Because the virtual view is in the relational format, users can query the data and the knowledge in a seamlessly integrated manner. To facilitate knowledge representation and inferencing within the database engine, our approach leverages XML support in hybrid relational-XML DBMSs (e.g., Microsoft SQL Server &amp; IBM DB2 9 PureXML). We provide a query rewriting mechanism to bridge the difference between logical and physical data modeling, so that queries on the virtual view can be automatically transformed to components that execute on the hybrid relational-XML engine in a way that is transparent to the user. 1.
Integrity Auditing of Outsourced Data.
An increasing number of enterprises outsource their IT services to third parties who can offer these services for a much lower cost due to economy of scale. Quality of service is a major concern in outsourcing. In particular, query integrity, which means that query results returned by the service provider are both correct and complete, must be assured. Previous work requires clients to manage data locally to audit the results sent back by the server, or database engine to be modified for generating authenticated results. In this paper, we introduce a novel integrity audit mechanism that eliminating these costly requirements. In our approach, we insert a small amount of records into an outsourced database so that the integrity of the system can be effectively audited by analyzing the inserted records in the query results. We study both randomized and deterministic approaches for generating the inserted records, as how these records are generated has significant implications for storage and performance. Furthermore, we show that our method is provable secure, which means it can withstand any attacks by an adversary whose computation power is bounded. Our analytical and empirical results demonstrate the effectiveness of our method. 1.
A Low%2DGranularity Classifier for Data Streams with Concept Drifts and Biased Class Distribution.

A data stream language and system designed for power and extensibility.
by
Fast Computation of Reachability Labeling for Large Graphs.
There are numerous applications that need to deal with a large graph and need to query reachability between nodes in the graph. A 2-hop cover can compactly represent the whole edge transitive closure of a graph in O(|V |  · |E | 1/2) space, and be used to answer reachability query efficiently. However, it is challenging to compute a 2-hop cover. The existing approaches suffer from either large resource consumption or low compression rate. In this paper, we propose a hierarchical partitioning approach to partition a large graph G into two subgraphs repeatedly in a top-down fashion. The unique feature of our approach is that we compute 2-hop cover while partitioning. In brief, in every iteration of top-down partitioning, we provide techniques to compute the 2-hop cover for connections between the two subgraphs first. A cover is computed to cut the graph into two subgraphs, which results in an overall cover with high compression for the entire graph G. Two approaches are proposed, namely a node-oriented approach and an edge-oriented approach. Our approach can efficiently compute 2-hop cover for a large graph with high compression rate. Our extensive experiment study shows that the 2-hop cover for a graph with 1,700,000 nodes and 169 billion connections can be obtained in less than 30 minutes with a compression rate about 40,000 using a PC.
Fast Computation of Reachability Labeling for Large Graphs.
There are numerous applications that need to deal with a large graph and need to query reachability between nodes in the graph. A 2-hop cover can compactly represent the whole edge transitive closure of a graph in O(|V |  · |E | 1/2) space, and be used to answer reachability query efficiently. However, it is challenging to compute a 2-hop cover. The existing approaches suffer from either large resource consumption or low compression rate. In this paper, we propose a hierarchical partitioning approach to partition a large graph G into two subgraphs repeatedly in a top-down fashion. The unique feature of our approach is that we compute 2-hop cover while partitioning. In brief, in every iteration of top-down partitioning, we provide techniques to compute the 2-hop cover for connections between the two subgraphs first. A cover is computed to cut the graph into two subgraphs, which results in an overall cover with high compression for the entire graph G. Two approaches are proposed, namely a node-oriented approach and an edge-oriented approach. Our approach can efficiently compute 2-hop cover for a large graph with high compression rate. Our extensive experiment study shows that the 2-hop cover for a graph with 1,700,000 nodes and 169 billion connections can be obtained in less than 30 minutes with a compression rate about 40,000 using a PC.
Dual Labeling Answering Graph Reachability Queries in Constant Time.
Graph reachability is fundamental to a wide range of applications, including XML indexing, geographic navigation, Internet routing, ontology queries based on RDF/OWL, etc. Many applications involve huge graphs and require fast answering of reachability queries. Several reachability labeling methods have been proposed for this purpose. They assign labels to the vertices, such that the reachability between any two vertices may be decided using their labels only. For sparse graphs, 2-hop based reachability labeling schemes answer reachability queries efficiently using relatively small label space. However, the labeling process itself is often too time consuming to be practical for large graphs. In this paper, we propose a novel labeling scheme for sparse graphs. Our scheme ensures that graph reachability queries can be answered in constant time. Furthermore, for sparse graphs, the complexity of the labeling process is almost linear, which makes our algorithm applicable to massive datasets. Analytical and experimental results show that our approach is much more efficient than stateof-the-art approaches. Furthermore, our labeling method also provides an alternative scheme to tradeoff query time for label space, which further benefits applications that use tree-like graphs. 1
Fast Relevance Discovery in Time Series.

LOCI Load Shedding through Class%2DPreserving Data Acquisition.

A Balanced Ensemble Approach to Weighting Classifiers for Text Classification.

Suppressing model overfitting in mining concept%2Ddrifting data streams.

Finding global icebergs over distributed data sets.

Discovering Frequent Closed Partial Orders from Strings.
Abstract—Mining knowledge about ordering from sequence data is an important problem with many applications, such as bioinformatics, Web mining, network management, and intrusion detection. For example, if many customers follow a partial order in their purchases of a series of products, the partial order can be used to predict other related customers ’ future purchases and develop marketing campaigns. Moreover, some biological sequences (e.g., microarray data) can be clustered based on the partial orders shared by the sequences. Given a set of items, a total order of a subset of items can be represented as a string. A string database is a multiset of strings. In this paper, we identify a novel problem of mining frequent closed partial orders from strings. Frequent closed partial orders capture the nonredundant and interesting ordering information from string databases. Importantly, mining frequent closed partial orders can discover meaningful knowledge that cannot be disclosed by previous data mining techniques. However, the problem of mining frequent closed partial orders is challenging. To tackle the problem, we develop Frecpo (for Frequent closed partial order), a practically efficient algorithm for mining the complete set of frequent closed partial orders from large string databases. Several interesting pruning techniques are devised to speed up the search. We report an extensive performance study on both real data sets and synthetic data sets to illustrate the effectiveness and the efficiency of our approach. Index Terms—Frequent patterns, closed patterns, partial orders, strings, data mining. 1
Catch the moment maintaining closed frequent itemsets over a data stream sliding window.
This paper considers the problem of mining closed frequent itemsets over a data stream  sliding window using limited memory space. We design a synopsis data structure to monitor  transactions in the sliding window so that we can output the current closed frequent  itemsets at any time. Due to time and memory constraints, the synopsis data structure cannot  monitor all possible itemsets. However, monitoring only frequent itemsets will make it  impossible to detect new itemsets when they become frequent. In this paper, we introduce  a compact data structure, the closed enumeration tree (CET), to maintain a dynamically  selected set of itemsets over a sliding window. The selected itemsets contain a boundary  between closed frequent itemsets and the rest of the itemsets. Concept drifts in a data  stream are reflected by boundary movements in the CET. In other words, a status change  of any itemset (e.g., from non-frequent to frequent) must occur through the boundary.
Compact reachability labeling for graph%2Dstructured data.
Testing reachability between nodes in a graph is a well-known problem with many important applications, including knowledge representation, program analysis, and more recently, biological and ontology databases inferencing as well as XML query processing. Various approaches have been proposed to encode graph reachability information using node labeling schemes, but most existing schemes only work well for specific types of graphs. In this paper, we propose a novel approach, HLSS(Hybrid Labeling of Sub-Structures), which identifies different types of substructures within a graph and encodes them using techniques suitable to the characteristics of each of them. We implement HLSS with an efficient two-phase algorithm, where the first phase identifies and encodes strongly connected components as well as tree substructures, and the second phase encodes the remaining reachability relationships by compressing dense rectangular submatrices in the transitive closure matrix. For the important subproblem of finding densest submatrices, we demonstrate the hardness of the problem and propose several practical algorithms. Experiments show that HLSS handles different types of graphs well, while existing approaches fall prey to graphs with substructures they are not designed to handle. Finally, we also discuss how to update reachability labels when the graph is updated, and qualitatively show that HLSS supports more efficient updates than existing approaches. 1
Stay Current and Relevant in Data Mining Research.

Online Mining of Data Streams Applications%2C Techniques and Progress.

On the Sequencing of Tree Structures for XML Indexing.
Sequence-based XML indexing aims at avoiding expensive join operations in query processing. It transforms structured XML data into sequences so that a structured query can be answered holistically through subsequence matching. In this paper, we address the problem of query equivalence with respect to this transformation, and we introduce a performance-oriented principle for sequencing tree structures. With query equivalence, XML queries can be performed through subsequence matching without join operations, post-processing, or other special handling for problems such as false alarms. We identify a class of sequencing methods for this purpose, and we present a novel subsequence matching algorithm that observe query equivalence. Still, query equivalence is just a prerequisite for sequence-based XML indexing. Our goal is to find the best sequencing strategy with regard to the time and space complexity in indexing and querying XML data. To this end, we introduce a performance-oriented principle to guide the sequencing of tree structures. For any given XML dataset, the principle finds an optimal sequencing strategy according to its schema and its data distribution. We present a novel method that realizes this principle. In our experiments, we show the advantages of sequence-based indexing over traditional XML indexing methods, and we compare several sequencing strategies and demonstrate the benefit of the performance-oriented sequencing principle.
On Reducing Classifier Granularity in Mining Concept%2DDrifting Data Streams.

Efficiently Mining Frequent Closed Partial Orders.


Pattern%2Dbased similarity search for microarray data.


Loadstar A Load Shedding Scheme for Classifying Data Streams.
We consider the problem of resource allocation in mining multiple data streams. Due to the large volume and the high speed of streaming data, mining algorithms must cope with the e#ects of system overload. How to realize maximum mining benefits under resource constraints becomes a challenging task. In this paper, we propose a load shedding scheme for classifying multiple data streams. We focus on the following problems: i) how to classify data that are dropped by the load shedding scheme? and ii) how to decide when to drop data from a stream? We introduce a quality of decision (QoD) metric to measure the level of uncertainty in classification when exact feature values of the data are not available because of load shedding. A Markov model is used to predict the distribution of feature values and we make classification decisions using the predicted values and the QoD metric. Thus, resources are allocated among multiple data streams to maximize the quality of classification decisions. Furthermore, our load shedding scheme is able to learn and adapt to changing data characteristics in the data streams. Experiments on both synthetic data and real-life data show that our load shedding scheme is e#ective in improving the overall accuracy of classification under resource constraints. keywords: data mining, data streams, load shedding, classification, quality of decision, feature prediction, Markov model.
Near%2DNeighbor Search in Pattern Distance Spaces.

A native extension of SQL for mining data streams.

Loadstar Load Shedding in Data Stream Mining.
In this demo, we show that intelligent load shedding is essential in achieving optimum results in mining data streams under various resource constraints. The Loadstar system introduces load shedding techniques to classifying multiple data streams of large volume and high speed. Loadstar uses a novel metric known as the quality of decision (QoD) to measure the level of uncertainty in classification. Resources are then allocated to sources where uncertainty is high. To make optimum classification decisions and accurate QoD measurement, Loadstar relies on feature prediction to model the data dropped by the load shedding mechanism. Furthermore, Loadstar is able to adapt to the changing data characteristics in data streams. The system thus offers a nice solution to data mining with resource constraints. 1
Mining Data Streams.
Abstract: Mining data streams has raised a number of research challenges for the data mining community. These challenges include the limitations of computational resources, especially because mining streams of data most likely be done on a mobile device with limited resources. Also due to the continuality of data streams, the algorithm should have only one pass or less over the incoming data records. In this article, our Algorithm Output Granularity (AOG) approach in mining data streams is discussed. AOG is a novel adaptable approach that can cope with the challenging inherent features of data streams. We also show the results for AOG based clustering in a resource constrained environment.
Preference%2DBased Frequent Pattern Mining.

An Improved Biclustering Method for Analyzing Gene Expression Profiles.

Mining Extremely Skewed Trading Anomalies.

Demand%2Ddriven frequent itemset mining using pattern structures.

Mining Extremely Skewed Trading Anomalies.

Moment Maintaining Closed Frequent Itemsets over a Stream Sliding Window.
This paper considers the problem of mining closed frequent itemsets over a sliding window using limited memory space. We design a synopsis data structure to monitor transactions in the sliding window so that we can output the current closed frequent itemsets at any time. Due to time and memory constraints, the synopsis data structure cannot monitor all possible itemsets. However, monitoring only frequent itemsets will make it impossible to detect new itemsets when they become frequent. In this paper, we introduce a compact data structure, the closed enumeration tree (CET), to maintain a dynamically selected set of itemsets over a sliding-window. The selected itemsets consist of a boundary between closed frequent itemsets and the rest of the itemsets. Concept drifts in a data stream are reflected by boundary movements in the CET. In other words, a status change of any itemset (e.g., from non-frequent to frequent) must occur through the boundary. Because the boundary is relatively stable, the cost of mining closed frequent itemsets over a sliding window is dramatically reduced to that of mining transactions that can possibly cause boundary movements in the CET. Our experiments show that our algorithm performs much better than previous approaches.
Active Mining of Data Streams.
Most previously proposed mining methods on data streams make an unrealistic assumption that “labelled” data stream is readily available and can be mined at anytime. However, in most real-world problems, labelled data streams are rarely immediately available. Due to this reason, models are reconstructed only when labelled data become available periodically. This passive stream mining model has several drawbacks. We propose a new concept of demand-driven active data mining. In active mining, the loss of the model is either continuously guessed without using any true class labels or estimated, whenever necessary, from a small number of instances whose actual class labels are verified by paying an affordable cost. When the estimated loss is more than a tolerable threshold, the model evolves by using a small number of instances with verified true class labels. Previous work on active mining concentrates on error guess and estimation. In this paper, we discuss several approaches on decision tree evolution. 1
XSeq An Index Infrastructure for Tree Pattern Queries.
Given a tree-pattern query, most XML indexing approaches decompose it into multiple sub-queries, and then join their results to provide the answer to the original query. Join operations have been identified as the most time-consuming
A Fast Algorithm for Subspace Clustering by Pattern Similarity.

Query Languages and Data Models for Database Sequences and Data Streams.
We study the fundamental limitations of relational  algebra (RA) and SQL in supporting  sequence and stream queries, and present effective  query language and data model enrichments  to deal with them. We begin by observing  the well-known limitations of SQL in  application domains which are important for  data streams, such as sequence queries and  data mining. Then we present a formal proof  that, for continuous queries on data streams,  SQL su#ers from additional expressive power  problems. We begin by focusing on the notion  of nonblocking (NB) queries that are the only  continuous queries that can be supported on  data streams. We characterize the notion of  nonblocking queries by showing that they are  equivalent to monotonic queries. Therefore  the notion of    for RA can be  formalized as its ability to express all monotonic  queries expressible in RA using only the  monotonic operators of RA. We show that RA  is not  NB-complete,  and SQL is not more  powerful than RA for monotonic queries.
Estimating the Selectivity of XML Path Expression with Predicates by Histograms.
Abstract. Selectivity estimation of path expressions in querying XML data plays an important role in query optimization. A path expression may contain multiple branches with predicates, each of which having its impact on the selectivity of the entire query. In this paper, we propose a novel method based on 2-dimensional value histograms to estimate the selectivity of path expressions embedded with predicates. The value histograms capture the correlation between the structures and the values in the XML data. We define a set of operations on the value histograms as well as on the traditional histograms that capture nodes positional distribution. We then construct a cost tree based on such operations. The selectivity of any node (or branch) in a path expression can be estimated by executing the cost tree. Compared with previous methods (which ignore value distribution) our method offers much better estimation accuracy. 1
Enhanced Biclustering on Expression Data.
molecular biology, which provide a powerful tool by which the expression patterns of thousands of genes can be monitored simultaneously and are already producing huge amount of valuable data. The concept of bicluster was introduced by Cheng and Church (2000) to capture the coherence of a subset of genes and a subset of conditions. A set of heuristic algorithms were also designed to either find one bicluster or a set of biclusters, which consist of iterations of masking null values and discovered biclusters, coarse and fine node deletion, node addition, and the inclusion of inverted data. These heuristics inevitably suffer from some serious drawback. The masking of null values and discovered biclusters with random numbers may result in the phenomenon of random interference which in turn impacts the discovery of high quality biclusters. To address this issue and to further accelerate the biclustering process, we generalize the model of bicluster to incorporate null values and propose a probabilistic algorithm (FLOC) that can discover a set of k possibly overlapping biclusters simultaneously. Furthermore, this algorithm can easily be extended to support additional features that suit different requirements at virtually little cost. Experimental study on the yeast gene expression data shows that the FLOC algorithm can offer substantial improvements over the previously proposed algorithm.
Indexing Weighted%2DSequences in Large Databases.
We present an index structure for managing weighted sequences in large databases. A weighted-sequence is defined as a two-dimensional structure where each element in the sequence is associated with a weight. A series of network events, for instance, is a weighted-sequence in that each event has a timestamp. Querying a large sequence database by events&#039; occurrence patterns is a first step towards understanding the temporal causal relationships among the events. The index structure proposed in this paper enables us to efficiently retrieve from the database all subsequences, possibly non-contiguous, that match a given query sequence both by events and by weights. The index method also takes into consideration the non-uniform frequency distribution of events in the sequence data. In addition, our method finds a broad range of applications in indexing scientific data consisting of multiple numerical columns for discovery of correlations among these columns. For instance, indexing a DNA micro-array that records expression levels of genes under different conditions enables us to search for genes whose responses to various experimental perturbations follow a given pattern. We demonstrate, using real-world data sets, that our method is effective and efficient.
MaPle A Fast Algorithm for Maximal Pattern%2Dbased Clustering.
mine different types of arbitrarily positioned and overlapping clusters of genetic data to find interesting patterns.
MaPle A Fast Algorithm for Maximal Pattern%2Dbased Clustering.
mine different types of arbitrarily positioned and overlapping clusters of genetic data to find interesting patterns.
Is random model better%3F On its accuracy and efficiency.

Inductive Learning in Less Than One Sequential Data Scan.

Mining concept%2Ddrifting data streams using ensemble classifiers.
Recently, mining data streams with concept drifts for actionable insights has become an important and challenging task for a wide range of applications including credit card fraud protection, target marketing, network intrusion detection, etc. Conventional knowledge discovery tools are facing two challenges, the overwhelming volume of the streaming data, and the concept drifts. In this paper, we propose a general framework for mining concept-drifting data streams using weighted ensemble classifiers. We train an ensemble of classification models, such as C4.5, RIPPER, naive Bayesian, etc., from sequential chunks of the data stream. The classifiers in the ensemble are judiciously weighted based on their expected classification accuracy on the test data under the time-evolving environment. Thus, the ensemble approach improves both the efficiency in learning the model and the accuracy in performing classification. Our empirical study shows that the proposed methods have substantial advantage over single-classifier approaches in prediction accuracy, and the ensemble framework is effective for a variety of classification models.
ATLaS A Native Extension of SQL for Data Mining.

Incompleteness of Database Languages for Data Streams and Data Mining the Problem and the Cure.

ViST A Dynamic Index Method for Querying XML Data by Tree Structures.
much research has been done in providing flexible query facilities to extract data from structured XML documents. In this paper, we propose ViST, a novel index structure for searching XML documents. By representing both XML documents and XML queries in structure-encoded sequences, we show that querying XML data is equivalent to finding subsequence matches. Unlike index methods that disassemble a query into multiple sub-queries, and then join the results of these sub-queries to provide the final answers, ViST uses tree structures as the basic unit of query to avoid expensive join operations. Furthermore, ViST provides a unified index on both content and structure of the XML documents, hence it has a performance advantage over methods indexing either just content or structure. ViST supports dynamic index update, and it relies solely on B    Trees without using any specialized data structures that are not well supported by DBMSs. Our experiments show that ViST is e#ective, scalable, and e#cient in supporting structural queries.
ATLAS A Small but Complete SQL Extension for Data Mining and Data Streams.
Introduction  DBMSs have long suffered from SQL&#039;s lack of power and extensibility. We have implemented ATLaS [1], a powerful database language and system that enables users to develop complete data-intensive applications in SQL---by writing new aggregates and table functions in SQL, rather than in procedural languages as in current Object-Relational systems. As a result, ATLaS&#039; SQL is Turing-complete [7], and is very suitable for advanced data-intensive applications, such as data mining and stream queries. The ATLaS system is now available for download along with a suite of applications [1] including various data mining functions, that have been coded in ATLaS&#039; SQL, and execute with a modest (20--40%) performance overhead with respect to the same applications written in C/C++. Our proposed demo will illustrate the key features and applications of ATLaS. In particular, we will demonstrate:  .  ATLaS&#039; SQL features, including its native support for user-defined aggregates and table functi
Recent Progress on Selected Topics in Database Research %2D A Report by Nine Young Chinese Researchers Working in the United States.

The Deductive Database System LDL  .
This paper describes the    system and the research advances that have enabled its design and development. We begin by discussing the new nonmonotonic and nondeterministic constructs that extend the functionality of the    language, while preserving its model-theoretic and fixpoint semantics. Then, we describe the execution model and the open architecture designed to support these new constructs and to facilitate the integration with existing DBMSs and applications. Finally, we describe the lessons learned by using    on various tested applications, such as middleware and datamining.
Pruning and Dynamic Scheduling of Cost%2DSensitive Ensembles.

An Index Structure for Pattern Similarity Searching in DNA Microarray Dat.

Extending SQL for Decision Support Applications.

A Fully Distributed Framework for Cost%2DSensitive Data Mining.
In this paper, we propose a fully distributed system (as compared to centralized and partially distributed systems) for cost-sensitive data mining. Experimental results have shown that this approach achieves higher accuracy than both the centralized and partially distributed learning methods, however, it incurs much less training time, neither communication nor computation overhead. 1.
The ATLaS System and Its Powerful Database Language Based on Simple Extensions of SQL.

delta%2DClusters Capturing Subspace Correlation in a Large Data Set.
Clustering has been an active research area of great practical importance for recent years. Most previous clustering models have focused on grouping objects with similar values on a (sub)set of dimensions (e.g., subspace cluster) and assumed that every object has an associated value on every dimension (e.g., bicluster). These existing cluster models may not always be adequate in capturing coherence exhibited among objects. Strong coherence may still exist among a set of objects (on a subset of attributes) even if they take quite different values on each attribute and the attribute values are not fully specified. This is very common in many applications including bio-informatics analysis as well as collaborative filtering analysis, where the data may be incomplete and subject to biases. In bio-informatics, a bicluster model has recently been proposed to capture coherence among a subset of the attributes. Here, we introduce a more general model, referred to as the ffi-cluster model, to capture coherence exhibited by a subset of objects on a subset of attributes, while allowing absent attribute values. A move-based algorithm (FLOC) is devised to efficiently produce a near-optimal clustering results. The ffi-cluster model takes the bicluster model as a special case, where the FLOC algorithm performs far superior to the bicluster algorithm. We demonstrate the correctness and efficiency of the ffi-cluster model and the FLOC algorithm on a number of real and synthetic data sets.
Progressive Modeling.
Presently, inductive learning is still performed in a frustrating batch process. The user has little interaction with the system and no control over the final accuracy and training time. If the accuracy of the produced model is too low, all the computing resources are misspent. In this paper, we propose a progressive modeling framework. In progressive modeling, the learning algorithm estimates online both the accuracy of the final model and remaining training time. If the estimated accuracy is far below expectation, the user can terminate training prior to completion without wasting further resources. If the user chooses to complete the learning process, progressive modeling will compute a model with expected accuracy in expected time. We describe one implementation of progressive modeling using ensemble of classifiers.
Empirical Comparison of Various Reinforcement Learning Strategies for Sequential Targeted Marketing.
We empirically evaluate the performance of various reinforcement learning methods in applications to sequential targeted marketing. In particular, we propose and evaluate a progression of reinforcement learning methods, ranging from the &#034;direct&#034; or &#034;batch&#034; methods to &#034;indirect&#034; or &#034;simulation based&#034; methods, and those that we call &#034;semidirect &#034; methods that fall between them. We conduct a number of controlled experiments to evaluate the performance of these competing methods. Our results indicate that while the indirect methods can perform better in a situation in which nearly perfect modeling is possible, under the more realistic situations in which the system&#039;s modeling parameters have restricted attention, the indirect methods&#039; performance tend to degrade. We also show that semi-direct methods are effective in reducing the amount of computation necessary to attain a given level of performance, and often result in more profitable policies.
User%2Ddirected Exploration of Mining Space with Multiple Attributes.

Mining Associations by Pattern Structure in Large Relational Tables.
Association rule mining aims at discovering patterns whose support is beyond a given threshold. Mining patterns composed of items described by an arbitrary subset of attributes in a large relational table represents a new challenge and has various practical applications, including the event management systems that motivated this work. The attribute combinations that define the items in a pattern provide the structural information of the pattern. Current association algorithms do not make full use of the structural information of the patterns: the information is either lost after it is encoded with attribute values, or is constrained by a given hierarchy or taxonomy. Pattern structures convey important knowledge about the patterns. In this paper, we present a novel architecture that organizes the mining space based on pattern structures. By exploiting the interrelationships among pattern structures, execution times for mining can be reduced significantly. This advantage is demonstrated by our experiments using both synthetic and real-life datasets.
A Framework for Scalable Cost%2Dsensitive Learning Based on Combing Probabilities and Benefits.

Clustering by pattern similarity in large data sets.
Clustering is the process of grouping a set of objects into classes of similar objects. Although definitions of similarity vary from one clustering model to another, in most of these models the concept of similarity is based on distances, e.g., Euclidean distance or cosine distance. In other words, similar objects are required to have close values on at least a set of dimensions. In this paper, we explore a more general type of similarity. Under the pCluster model we proposed, two objects are similar if they exhibit a coherent pattern on a subset of dimensions. For instance, in DNA microarray analysis, the expression levels of two genes may rise and fall synchronously in response to a set of environmental stimuli. Although the magnitude of their expression levels may not be close, the patterns they exhibit can be very much alike. Discovery of such clusters of genes is essential in revealing significant connections in gene regulatory networks. E-commerce applications, such as collaborative filtering, can also benefit from the new model, which captures not only the closeness of values of certain leading indicators but also the closeness of (purchasing, browsing, etc.) patterns exhibited by the customers. Our paper introduces an effective algorithm to detect such clusters, and we perform tests on several real and synthetic data sets to show its effectiveness.
The Deductive Database System LDL  
This paper describes the    system and the research advances that have enabled its design and development. We begin by discussing the new nonmonotonic and nondeterministic constructs that extend the functionality of the    language, while preserving its model-theoretic and fixpoint semantics. Then, we describe the execution model and the open architecture designed to support these new constructs and to facilitate the integration with existing DBMSs and applications. Finally, we describe the lessons learned by using    on various tested applications, such as middleware and datamining.
Discovery in multi%2Dattribute data with user%2Ddefined constraints.

FARM A Framework for Exploring Mining Spaces with Multiple Attributes.

SSDT A Scalable Subspace%2DSplitting Classifier for Biased Data.

The S2%2DTree  An Index Structure for Subsequence Matching of Spatial Objects.
We present the S²-Tree, an indexing method for subsequence matching of spatial objects. The S²-Tree locates subsequences within a collection of spatial sequences, i.e., sequences made up of spatial objects, such that the subsequences match a given query pattern within a specified tolerance. Our method is based on (i) the string-searching techniques that locate substrings within a string of symbols drawn from a discrete alphabet (e.g., ASCII characters) and (ii) the spatial access methods that index (unsequenced) spatial objects. Particularly, the S²-Tree can be applied to solve problems such as subsequence matching of time-series data, where features of subsequences are often extracted and mapped into spatial objects. Moreover, it supports queries such as &#034;what is the longest common pattern of the two time series?&#034;, which previous subsequence matching algorithms find difficult to solve efficiently.
Database System Extensions for Decision Support the AXL Approach.

User Defined Aggregates in Object%2DRelational Systems.
User-defined aggregates are essential in many advanced database applications, particularly in expressing data mining functions, but they find little support in current systems including Object-Relational databases. Three serious limitations of current systems are (i) the inability of introducing new aggregates (e.g., by coding them in procedural language as originally proposed in SQL3), (ii) the inability of returning partial results during the computation (e.g., to support online aggregation), and (iii) the inability of using aggregates in recursive queries (e.g., to express Bill of Materials and optimized graph searches). In this paper, we presents a unified solution to these problems which realizes SQL3 original proposal for user-defined aggregates (UDAs) , and adds significant improvements in terms of expressive power and ease of use: in fact our SQL-AG system also supports online aggregation, monotonic aggregation, and a high-level aggregate definition language named SADL. We focu...
Landmarks a New Model for Similarity%2Dbased Pattern Querying in Time Series Databases.
In this paper we present the Landmark Model, a model for time series that yields new techniques for similarity-based time series pattern querying. The Landmark Model does not follow traditional similarity models that rely on pointwise Euclidean distance. Instead, it leads to Landmark Similarity, a general model of similarity that is consistent with human intuition and episodic memory. By tracking different specific subsets of features of landmarks, we can efficiently compute different Landmark Similarity measures that are invariant under corresponding subsets of six transformations; namely, Shifting, Uniform
CMP A Fast Decision Tree Classifier Using Multivariate Predictions.
Most decision tree classifiers are designed to keep class histograms for single attributes, and to select a particular attribute for the next split using said histograms. In this paper, we propose a technique where, by keeping histograms on attribute pairs, we achieve (i) a significant speed-up over traditional classifiers based on single attribute splitting, and (ii) the ability of building classifiers that use linear combinations of values from non-categorical attribute pairs as split criterion. Indeed, by keeping two-dimensional histograms, CMP can often predict the best successive split, in addition to computing the current one; therefore, CMP is normally able to grow more than one level of a decision tree for each data scan. CMP’s performance improvements are also due to techniques whereby non-categorical attributes are discretized without loss in classification accuracy; in fact, we introduce simple techniques, whereby classification errors caused by discretization at one step can then be corrected in the following step. In summary, CMP represents a unified algorithm that extends the functionality of existing classifiers and improves their performance. 1.
Using SQL to Build New Aggregates and Extenders for Object%2D Relational Systems.
User-defined Aggregates (UDAs) provide a  versatile mechanism for extending the power  and applicability of Object-Relational  Databases (O-R DBs). In this paper, we describe  the AXL system that supports an SQLbased  language for introducing new UDAs.  AXL is easy to learn and use for database programmers  because it preserves the constructs,  programming paradigm and data types  of SQL (whereas there is an `impedance  mismatch&#039; between SQL and the procedural  languages of user-defined functions currently  used in O-R DBs). AXL will also inherit the  benefits of database query languages, such as  scalability, data independence and parallelizability.  In this paper, we show that, while  adding only minimal extensions to SQL, AXL  is very powerful and capable of expressing  complex algorithms e#ciently. We demonstrate  this by coding data mining functions  and other advanced applications that, previously,  had been a major problem for SQL  databases.  Due to its flexibility, SQL-compati...
User Defined Aggregates for Logical Data Languages.
A new wave of data-intensive and knowledge-based applications---such as data mining and decision support---require the introduction of complex application-specific aggregate functions. In this paper, we propose extensions for deductive database systems to support these new applications. We develop constructs, formal semantics, and implementation techniques for user-defined aggregates, and describe their realization in an extended LDL++ system recently built at UCLA. With these extensions, the system can support online aggregation, roll-ups for data cubing, temporal aggregates for time-series, iceberg queries, and other recently proposed operators used in decision support and data mining procedures. We then discuss the application of this technology to other DBMSs, and in particular to the SQL3 specifications that support the notion of user-defined aggregates. We show that SQL3 suffers from limitations that severely restrict its use in new applications; thus we propose simple extensio...
User%2DDefined Aggregates for Datamining.
User-defined aggregates can be the linchpin of sophisticated datamining functions and other advanced database applications. This is demonstrated by our efficient implementation on DB2 of SQL3 user-defined aggregates extended with early returns, which we have used to implement several data mining algorithms. Aggregates with early returns are monotonic and can thus be used freely in recursive queries. 1 Introduction  The importance of rollups and data cubes in decision support is universally recognized, and these aggregates have now become sine qua non built-ins in the new releases of commercial DBMSs. Yet, we claim that both researchers and vendors have overlooked UserDefined Aggregates (UDA)s, which can play an even more critical and pervasive role in database-centric data mining applications. Indeed, we show that:  ffl Many data mining algorithms rely on specialized aggregates.  ffl The number and diversity of these aggregates implies that (rather than vendors adding ad hoc builtins, ...
User%2DDefined Aggregates in Database Languages.
User-defined aggregates can be the linchpin of sophisticated datamining functions and other advanced database applications, but they find little support in current database systems including Object-Relational databases. Three serious limitations of current databases are (i) the inability of introducing new aggregates (e.g., by coding them in a procedural language as proposed in SQL3), (ii) the inability of returning partial results during computation (e.g., to support online aggregation), and (iii) the inability of using aggregates in recursive queries---e.g., to express Bill of Materials (BoM) applications and optimized graph searches. This paper proposes a unified solution to these problems, and discusses practical and theoretical aspects of this powerful addition to database languages.  1 Introduction  The importance of new specialized aggregates in advanced applications is exemplified by rollups and data cubes that, owing to their use in decision support applications, are now sine ...
User Defined Aggregates for Logical Data Languages.
A new wave of data-intensive and knowledge-based applications---such as data mining and decision support---require the introduction of complex application-specific aggregate functions. In this paper, we propose extensions for deductive database systems to support these new applications. We develop constructs, formal semantics, and implementation techniques for user-defined aggregates, and describe their realization in an extended LDL++ system recently built at UCLA. With these extensions, the system can support online aggregation, roll-ups for data cubing, temporal aggregates for time-series, iceberg queries, and other recently proposed operators used in decision support and data mining procedures. We then discuss the application of this technology to other DBMSs, and in particular to the SQL3 specifications that support the notion of user-defined aggregates. We show that SQL3 suffers from limitations that severely restrict its use in new applications; thus we propose simple extensio...
